package algorithm.swordoff;

/**
 * 礼物的最大价值
 */

public class SQ47 {

    public int maxValue(int[][] grid) {
        int[][] profit = new int[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) profit[i][j] = grid[i][j];
                else if (i == 0) profit[i][j] = profit[i][j-1] + grid[i][j];
                else if (j == 0) profit[i][j] = profit[i-1][j] + grid[i][j];
                else profit[i][j] = Math.max(profit[i-1][j], profit[i][j-1]) + grid[i][j];
            }
        }

        return profit[grid.length-1][grid[0].length-1];

    }

}
